class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# class Solution(object):
#     def lcaDeepestLeaves(self, root):
#         """
#         :type root: TreeNode
#         :rtype: TreeNode
#         """
#         self.out = None
#         self.max_depth = 0
#
#         def dfs(node, now):
#             left_depth = 0
#             right_depth = 0
#             if node.left:
#                 left_depth = dfs(node.left, now + 1)
#             if node.right:
#                 right_depth = dfs(node.right, now + 1)
#             if left_depth == right_depth:
#                 if left_depth + right_depth + now > self.max_depth:
#                     self.out = node
#                     self.max_depth = left_depth + right_depth + now
#             return max(left_depth, right_depth) + 1
#
#         dfs(root, 1)
#
#         return self.out
class Solution(object):
    def lcaDeepestLeaves(self, root):
        st = [root]
        d = {}
        while True:
            next_st = []
            for node in st:
                if node.left:
                    next_st.append(node.left)
                    d[node.left] = node
                if node.right:
                    next_st.append(node.right)
                    d[node.right] = node
            if not next_st:
                break
            else:
                st = next_st
        while len(st) > 1:
            next_st = set()
            for node in st:
                next_st.add(d[node])
            st = next_st

        return st.pop()



